#include "headfiles.h"

using namespace std;

/*
static int twoArrayMedianRecur(int *a1, int n1, int *a2, int n2, int left, int right) {
    if (left > right) {
        int l = (n1 + n2 - 1) / 2 - n1;
        if (l < 0) {
            l = 0;
        }

        int r = (n1 + n2 - 1) / 2;
        if (r >= n2) {
            r = n2 - 1;
        }

        return twoArrayMedianRecur(a2, n2, a1, n1, l, r);

        int i = (left + right) / 2;
        int j = (n1 + n2 - 1) / 2 - i;
        if ((j == 0 || a1[i] > a2[j]) && 
            (j == n2 || a1[i] <= a2[j + 1])) {
            return a1[i];
        }
        else if ((j == 0 || a1[i] > a2[j]) &&
                 (j != n2) &&
                 a1[i] > a2[j + 1]) {
            return twoArrayMedianRecur(a1, n1, a2, n2, left, i - 1);
        }
        else {
            return twoArrayMedianRecur(a1, n1, a2, n2, i + 1, right);
        }
    }
}

int twoArrayMedian(int *a1, int n1, int *a2, int n2) {
    int left = (n1 + n2 - 1) / 2 - n2;
    if (left < 0) {
        left = 0;
    }

    int right = (n1 + n2 - 1) / 2;
    if (right >= n1) {
        right = n1 - 1;
    }

    return twoArrayMedianRecur(a1, n1, a2, n2, left, right);
}

// Assume n1 > n2
int twoArrayMedianImpl(int *a1, int n1, int *a2, int n2) {
    if (a1[0] >= a2[n2 - 1]) {
        return a1[(n1 + n2 - 1) / 2 - n2];
    }

    if (a2[0] >= a1[n1 - 1]) {
        return a1[(n1 + n2 - 1) / 2];
    }

    int left, right;
    int index1, index2;
    left = 0;
    right = n2 - 1;
    index2 = (left + right) / 2;
    index1 = (n1 + n2 - 1) / 2 - index2;
    while (left < right) {
        if (a1[index1] == a2[index2]) {
            return a1[index1];
        }
        else if (a1[index1] < a2[index2]) {
            if (a2[index2] <= a1[index1 + 1]) {
                return a2[index2];
            }
            else {
                right = index2 - 1;
            }
        }
        else { // a1[index1] > a2[index2]
            if (a1[index1 - 1] <= a2[index2]) {
                return a2[index2];
            }
            else {
                left = index2 + 1;
            }
        }

        index2 = (left + right) / 2;
        index1 = (n1 + n2 - 1) / 2 - index2;
    }

    return a2[left];
}

double twoArrayMedianDouble(int *a, int m, int *b, int n) {

}
*/

// Median of one single sorted array
static double medianSortedArray(int *a, int n) {
    if ((n & 1)) {
        return a[n/2];
    }
    else {
        double sum = a[n/2] + a[n/2 - 1];
        return sum/2;
    }
}

static int min_val(int a, int b) {
    return (a < b) ? a : b;
}

static int max_val(int a, int b) {
    return (a > b) ? a : b;
}

double medianOf4Elems(int *a, int *b) {
    if (a[1] >= b[1]) {
        if (a[0] >= b[1]) {
            return (a[0] + b[1]) / 2.0;
        }
        else {
            if (a[0] <= b[0]) {
                return (b[0] + b[1]) / 2.0;
            }
            else {
                return (a[0] + b[1]) / 2.0;
            }
        }
    }
    else {
        if (b[0] >= a[1]) {
            return (b[0] + a[1]) / 2.0;
        }
        else {
            if (b[0] <= a[0]) {
                return (a[0] + a[1]) / 2.0;
            }
            else {
                return (b[0] + a[1]) / 2.0;
            }
        }
    }
}

double medianOf3Elems(int *a, int *b) {
    if (b[0] >= a[1]) {
        return a[1];
    }
    else {
        if (b[0] >= a[0]) {
            return b[0];
        }
        else {
            return a[0];
        }
    }
}

double medianBaseCase(int med, int *a, int n) {
    if (n & 1) { // n is odd
        int index = (n - 1) / 2; // n is 1
        if (index == 0) {
            double sum = med + a[0];
            return sum / 2;
        }
        else {
            if (med >= a[index + 1]) {
                double sum = a[index] + a[index + 1];
                return sum / 2;
            }
            else if (med >= a[index - 1]) {
                double sum = med + a[index];
                return sum / 2;
            }
            else { // med < a[index - 1];
                double sum = a[index - 1] + a[index];
                return sum / 2;
            }
        }
    }
    else {   // n is even
        int index = n / 2;
        if (med >= a[index]) {
            return a[index];
        }
        else if (med >= a[index - 1]) {
            return med;
        }
        else {
            return a[index - 1];
        }
    }
}

double medianBaseCase2(int med1, int med2, int *a, int n) {
    if (n & 1) {
        int index = (n - 1) / 2;
        if (med1 >= a[index + 1]) {
            return a[index + 1];
        }
        else if (med2 <= a[index - 1]) {
            return a[index - 1];
        }
        else { // med1 < a[index + 1], med2 > a[index - 1]
            if (med2 >= a[index]) {
                if (med1 > a[index]) {
                    return med1;
                }
                else {
                    return a[index];
                }
            }
            else { // med2 < a[index]
                return med2;

            }
        }
    }
    else { // n is even
        int index = n / 2 - 1;
        double sum;
        if (med1 >= a[index + 1]) {
            if (n > 2) {
                sum = min_val(a[index + 2], med1) + a[index + 1];
                return sum / 2;
            }
            else {
                sum = med1 + a[index + 1];
                return sum / 2;
            }
        }
        else if (med2 < a[index]) {
            if (n > 2) {
                sum = max_val(a[index - 1], med2) + a[index];
                return sum / 2;
            }
            else {
                sum = med2 + a[index];
                return sum / 2;
            }
        }
        else {
            if (med2 > a[index + 1]) {
                sum = max_val(a[index], med1) + a[index + 1];
                return sum / 2;
            }
            else { // med2 <= a[index + 1]
                sum = max_val(a[index], med1) + med2;
                return sum / 2;
            }
        }
    
    }
}



double twoArrayMedianDouble(int *a, int m, int *b, int n) {
    if (m == 1 && n == 1) {
        double sum = a[0] + b[0];
        return sum / 2.0;
    }
    else if (m == 0) {
        return medianSortedArray(b, n);
    }
    else if (n == 0) {
        return medianSortedArray(a, m);
    }
    else if (n == 1) {
        return medianBaseCase(b[0], a, m);
    }
    else if (m == 1) {
        return medianBaseCase(a[0], b, n);
    }
    else if (m == 2) {
        return medianBaseCase2(a[0], a[1], b, n);
    }
    else if (n == 2) {
        return medianBaseCase2(b[0], b[1], a, m);
    }

    int median_i = m / 2;
    int median_j = n / 2;
    if (a[median_i] <= b[median_j]) {
        int dispose_i = (m % 2 == 0) ? median_i - 1 : median_i;
        int dispose_j = n - median_j - 1;
        int dispose = min_val(dispose_i, dispose_j);
        return twoArrayMedianDouble(&a[dispose], m - dispose, b, n - dispose);
    }
    else {
        int dispose_i = m - median_i - 1;
        int dispose_j = (n % 2 == 0) ? median_j - 1 : median_j;
        int dispose = min_val(dispose_i, dispose_j);
        return twoArrayMedianDouble(a, m - dispose, &b[dispose], n - dispose);
    }
}

/*
double findMedian(int A[], int B[], int l, int r, int nA, int nB) {
    if (l>r) {
        return findMedian(B, A, max(0, (nA+nB)/2-nA), min(nB,(nA+nB)/2), nB, nA);
    }

    int i = (l+r)/2;
    int j = (nA+nB)/2 – i – 1;
    if (j>=0 && A[i] < B[j]) {
        return findMedian(A, B, i+1, r, nA, nB);
    }
    else if (j<nB-1 && A[i] > B[j+1]) {
        return findMedian(A, B, l, i-1, nA, nB);
    }
    else {
        if ( (nA+nB)%2 == 1 ) {
            return A[i];
        }
        else if (i>0) {
            return (A[i]+max(B[j], A[i-1]))/2.0;
        }
        else {
            return (A[i]+B[j])/2.0;
        }
    }
}

double findMedianSortedArrays(int A[], int n, int B[], int m) {
    if (n<m) {
        return findMedian(A, B, 0, n-1, n, m);
    }
    else {
        return findMedian(B, A, 0, m-1, m, n);
    }
}
*/
